package com.example.algorithm.sorts;

public class InsertSort {

    public static void main(String[] args) {

        int[] nums = {3,5,7,4,2,9,1,3};
        insertSort(nums);

        for (int num : nums) {
            System.out.print(num + ",");
        }

    }

    public static void insertSort(int[] nums) {
        for (int i = 1; i < nums.length; i++) {
            int tmp = nums[i];
            for (int j = i - 1; j >= 0; j--) {
                if (nums[j] > tmp) {
                    nums[j + 1] = nums[j];
                    if (j == 0) { // 到了数组头还没找到比当前值小的，说明当前元素为最小的
                        nums[j] = tmp;
                    }
                } else {
                    nums[j + 1] = tmp;
                    break;
                }

            }
        }

    }
}
